Global positioning systems allow automatic route calculation from a current position to a destination location. Such systems guide a driver of a vehicle along a calculated trip route from the particular instantaneous vehicle location to the destination location by outputting trip instructions in conjunction with a visual display of route segments as the vehicle progresses.
One exemplary geographical position location system receives and analyzes location parameters derived from the Global Positioning System (GPS), a radio-navigation system, developed and operated by the U.S. Defense Department, which includes a series of 24 constellation satellites orbiting the earth at a distance of approximately 20,000 kilometers. The GPS position location parameters permit wireless device processors to determine their respective three dimensional positions and velocities using very precise location parameters and timing signals received from the satellites.
The displays on many portable GPS devices are small and the data populating the screen must be efficiently presented. Care must be taken to prevent overcrowding the screen with too much data. Furthermore, text labels accompanying objects should be accurately positioned so as to best associate the text with the object, i.e. road, river, etc., with minimal crossovers and crowding.
Accordingly, the interest and the demand of finding efficient map labeling methods is increasing. Most discussions of map labeling are concentrating on straight line, horizontal or slant, based labeling. However, not all roads and rivers are straight objects wherein their accompanying text may be drawn on a baseline calculated using a linear equation of the form y=mx+b. Curved labeling may deliver better results for labeling map polylines such as rivers and roads because it can be more faithful to the original polylines.
Alexander Wolff provides in reference [1] a method of curved labeling by generating circular arcs. The method executes in O(n2) time, where n is the number of points of the polyline.
However, the number of points of polylines can be very large and the computation burden of generating curved labels may compromise the map drawing performance of a handheld or vehicle navigation GPS device.
Accordingly there is a need for apparatus and methods that efficiently generate curved labels for maps drawn on portable GPS devices.
[1] Alexander Wolff, Lars Knipping, Marc van Kreveld, Tycho Strijk and Pankaj K. Agarwal, 2002, A Simple and Efficient Algorithm for High-quality Line Labeling. http://i11www.iti.uni-karlsruhe.de/map-labeling/papers/wkksa-seahq-00.pdf